This invention relates to devices and methods for performing a fast Fourier transform.
The fast Fourier transform (FFT) is an important algorithm in the field of signal processing. It is used to calculate the discrete Fourier transform (DFT) efficiently. In order to meet high performance and real-time requirements of modern applications, hardware designers have tried to implement efficient architectures for the computation of the FFT. In this context, pipelined hardware architectures have been used because they provide high throughputs and low latencies suitable for real-time applications.
There are two main types of pipelined architectures: feedback and feedforward. Feedback architectures have feedback loops where some outputs of the butterfly computation at a stage in the pipeline is fed back to the input of the same stage. In feedforward architectures a continuous flow of samples is processed through the stages in the pipeline. Each stage in the pipeline passes the processed data on to the next stage. Both the feedback and feedforward architectures may also be capable of processing more than one sample in parallel.
In current real-time applications, the FFT has to be calculated at very high throughput rates, e.g. in the range of GSamples/s. These high-performance requirements appear in applications such as Orthogonal Frequency Division Multiplexing (OFDM) and Ultra Wideband (UWB). In this context a number of challenges exist. For example, the FFT of multiple independent data sequences may need to be calculated and each data sequence may have several samples which are received in parallel. This may require parallel feedback or feedforward pipelined architectures which can manage several samples in parallel and provide improvements in throughput.
Hardware engineers often design FFT pipelines based on the FFT size requirements of the particular hardware application. Such pipelined architectures work well for a particular FFT size (which is also referred to as “FFT length”). However, if an application requires support for multiple FFT sizes, multiple pipelines are required—one pipeline for each FFT size. Providing multiple pipelines requires greater chip area and increases the cost of the chip. There is, therefore, a need for FFT pipeline architecture which supports multiple FFT sizes and is cost and chip area efficient.